package com.shm.leetcode;

/**
 * 319. 灯泡开关
 * 初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭一个。
 *
 * 第三轮，你每三个灯泡就切换一个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换一个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。
 *
 * 找出并返回 n 轮后有多少个亮着的灯泡。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：n = 3
 * 输出：1
 * 解释：
 * 初始时, 灯泡状态 [关闭, 关闭, 关闭].
 * 第一轮后, 灯泡状态 [开启, 开启, 开启].
 * 第二轮后, 灯泡状态 [开启, 关闭, 开启].
 * 第三轮后, 灯泡状态 [开启, 关闭, 关闭].
 *
 * 你应该返回 1，因为只有一个灯泡还亮着。
 * 示例 2：
 *
 * 输入：n = 0
 * 输出：0
 * 示例 3：
 *
 * 输入：n = 1
 * 输出：1
 *
 *
 * 提示：
 *
 * 0 <= n <= 109
 * @author SHM
 */
public class BulbSwitch {
    /**
     * 数学
     * 这是一道经典的数论题。
     *
     * 整理一下题意：第 ii 轮改变所有编号为 ii 的倍数的灯泡的状态（其中灯泡编号从 11 开始）。
     *
     * 一个编号为 xx 的灯泡经过 nn 轮后处于打开状态的充要条件为「该灯泡被切换状态次数为奇数次」。
     *
     * 同时，一个灯泡切换状态的次数为其约数的个数（去重）。
     *
     * 于是问题转换为：在 [1,n][1,n] 内有多少个数，其约数的个数为奇数。这些约数个数为奇数的灯泡就是最后亮着的灯泡。
     *
     * 又根据「约数」的定义，我们知道如果某个数 kk 为 xx 的约数，那么 \frac{x}{k}
     * k
     * x
     * ​
     *   亦为 xx 的约数，即「约数」总是成对出现，那么某个数的约数个数为奇数，意味着某个约数在分解过程中出现了 22 次，且必然重复出现在同一次拆解中，即 k = \frac{x}{k}k=
     * k
     * x
     * ​
     *  ，即有 xx 为完全平方数（反之亦然）。
     *
     * 问题最终转换为：在 [1,n][1,n] 中完全平方数的个数为多少。
     *
     * 根据数论推论，[1,n][1,n] 中完全平方数的个数为 \left \lfloor \sqrt{n} \right \rfloor⌊
     * n
     * ​
     *  ⌋，即最后亮着的灯泡数量为 \left \lfloor \sqrt{n} \right \rfloor⌊
     * n
     * ​
     *  ⌋。
     *  数学
     * 这是一道经典的数论题。
     *
     * 整理一下题意：第 ii 轮改变所有编号为 ii 的倍数的灯泡的状态（其中灯泡编号从 11 开始）。
     *
     * 一个编号为 xx 的灯泡经过 nn 轮后处于打开状态的充要条件为「该灯泡被切换状态次数为奇数次」。
     *
     * 同时，一个灯泡切换状态的次数为其约数的个数（去重）。
     *
     * 于是问题转换为：在 [1,n][1,n] 内有多少个数，其约数的个数为奇数。这些约数个数为奇数的灯泡就是最后亮着的灯泡。
     *
     * 又根据「约数」的定义，我们知道如果某个数 kk 为 xx 的约数，那么 \frac{x}{k}
     * k
     * x
     * ​
     *   亦为 xx 的约数，即「约数」总是成对出现，那么某个数的约数个数为奇数，意味着某个约数在分解过程中出现了 22 次，且必然重复出现在同一次拆解中，即 k = \frac{x}{k}k=
     * k
     * x
     * ​
     *  ，即有 xx 为完全平方数（反之亦然）。
     *
     * 问题最终转换为：在 [1,n][1,n] 中完全平方数的个数为多少。
     *
     * 根据数论推论，[1,n][1,n] 中完全平方数的个数为 \left \lfloor \sqrt{n} \right \rfloor⌊
     * n
     * ​
     *  ⌋，即最后亮着的灯泡数量为 \left \lfloor \sqrt{n} \right \rfloor⌊
     * n
     * ​
     *  ⌋。
     *
     * 作者：AC_OIer
     * 链接：https://leetcode-cn.com/problems/bulb-switcher/solution/gong-shui-san-xie-jing-dian-shu-lun-tui-upnnb/
     * @param n
     * @return
     */
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }
}
